'''
https://leetcode.cn/problems/minimum-interval-to-include-each-query/description/

'''
import heapq
from collections import defaultdict
from typing import List


class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        m, n = len(intervals), len(queries)
        intervals.sort()        # 以左边界排序
        idx_dict = defaultdict(list)
        for i, query in enumerate(queries):
            idx_dict[query].append(i)
        queries.sort()
        res = [0] * len(queries)

        heap = []        # 0:区间长度，1:区间结束位置

        i, j = 0, 0
        while j < n:
            while i < m and intervals[i][0] <= queries[j]:
                heapq.heappush(heap, (intervals[i][1] - intervals[i][0] + 1, intervals[i][1]))
                i += 1
            while heap and heap[0][1] < queries[j]:
                heapq.heappop(heap)
            for k in idx_dict[queries[j]]:
                res[k] = -1 if not heap else heap[0][0]
            j += 1
        return res


intervals = [[4,5],[5,8],[1,9],[8,10],[1,6]]
queries = [7,9,3,9,3]
print(Solution().minInterval(intervals, queries))